package com.yangzhe.algorithm.c036;

import java.util.HashMap;
import java.util.Map;

// 二叉树的最大特殊宽度，java版
// 测试链接 : https://leetcode.cn/problems/maximum-width-of-binary-tree/
public class Code03_WidthOfBinaryTree1_LeetCode {

    // 不提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    private static TreeNode[] queue = new TreeNode[3001];

    private static Map<TreeNode, Integer> indexMap;

    private static int l, r = 0;

    /**
     * 本题相当于要把null算成一层的占位，也就是当作完全二叉树处理，遍历的时候把null也当作一个节点，但是此方法效率比较低。可以使用如下算法：
     * 基础认知：[1,2,3,4,5...]的数组就是完全二叉树BFS打印的顺序，所以每层index都是连续的，最右index-最左index就是当前层的宽度
     * <p>
     * 1. 用优化过的BFS算法，需要知道遍历的是哪一层
     * 2. 遍历每层过程中，用额外的空间记录下一层的，每一个节点在完全二叉树中映射到数组组中的位置 左节点index = 2 * index，右节点index = 2 * index + 1
     * 3. 遍历每层过程中，计算：每层当前节点宽度 = 最右节点index - 最左节点index + 1
     * 4. 取最大值即可
     *
     * @param root
     * @return
     */
    public static int widthOfBinaryTree(TreeNode root) {
        int result = 0;
        l = r = 0;
        indexMap = new HashMap<>();

        if (root != null) {
            queue[r++] = root;
            indexMap.put(root, 1);
            while (l != r) {
                int size = r - l;

                int leftIndex = indexMap.get(queue[l]);
                int rightIndex = indexMap.get(queue[r - 1]);

                result = Math.max(result, rightIndex - leftIndex + 1);
                for (int i = 0; i < size; i++) {
                    TreeNode treeNode = queue[l++];
                    int index = indexMap.get(treeNode);
                    if (treeNode.left != null) {
                        queue[r++] = treeNode.left;
                        indexMap.put(treeNode.left, 2 * index);
                    }

                    if (treeNode.right != null) {
                        queue[r++] = treeNode.right;
                        indexMap.put(treeNode.right, 2 * index + 1);
                    }
                }

            }
        }

        return result;
    }
}
